package oj;

//合并两个有序链表
public class Num25 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }else if(l2 == null){
            return l1;
        }

        ListNode mergeHead = null;

        if(l1.val <= l2.val){
            mergeHead = l1;
            mergeHead.next = mergeTwoLists(l1.next,l2);
        }else {
            mergeHead = l2;
            mergeHead.next = mergeTwoLists(l1,l2.next);
        }
        return mergeHead;
    }

    //链表分割
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if(pHead == null){
            return null;
        }
        ListNode pLessHead = new ListNode();
        ListNode pLessTail = new ListNode();
        ListNode pGreatHead = new ListNode();
        ListNode pGreatTail = new ListNode();

        while (pHead != null){
            if (pHead.val < x){
                pLessTail.next = pHead;
                pLessTail = pHead;
            }else {
                pGreatTail.next = pHead;
                pLessTail = pHead;
            }
            pHead = pHead.next;
        }

        pLessTail.next = pGreatHead.next;
        pGreatTail.next = null;
        pHead = pLessHead.next;

        return pHead;
    }


    //删除链表重复节点
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead == null){
            return null;
        }
        ListNode prev = null;
        ListNode node = pHead;
        ListNode nextNode = node.next;

        while (nextNode != null){
            if(node.val != nextNode.val){
                prev = node;
                node = nextNode;
                nextNode = nextNode.next;
            }else {
                while (nextNode != null && nextNode.val == node.val) {
                    nextNode = nextNode.next;
                }
                if (prev == null) {
                    pHead = nextNode;
                } else {
                    prev.next = nextNode;
                }
                while (node != nextNode) {
                    ListNode p = node;
                    node = node.next;
                }
                if (nextNode != null) {
                    nextNode = nextNode.next;
                }
            }
        }
        return pHead;
    }


















}

